package 链表.easy;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *  环形链表
 * @author Lw中
 * @date 2020/9/21 11:23
 */
public class YiSiYi {

    class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
      ListNode() {
          next = null;
      }
    }

    public boolean hasCycle(ListNode head) {
        /** 方法一：使用hashset循环存储链表的各个节点 */
//        Set<ListNode> hashSet = new HashSet<>();
//        while(head != null) {
//            if (hashSet.contains(head)) {
//                return true;
//            } else {
//                hashSet.add(head);
//            }
//            head = head.next;
//        }
//        return false;

        /** 方法二：使用双指针 */

        // 形成环必须要有三个节点：如果头结点的下一个节点和下下个节点为空就返回false
//        if (head == null || head.next == null) {
//            return false;
//        }
//        ListNode fast = head;
//        ListNode low = head;
//        while (low != fast) {
//            if (fast == null) {
//                return false;
//            }
//            fast = fast.next.next;
//            low = low.next;
//        }
//        return true;
        ListNode fast = head;
        ListNode low = head;
        while (fast != null && fast.next != null && fast.next.next != null) {
            low = low.next;
            fast = fast.next.next;
            if (low == fast) {
                return true;
            }
        }
        return  false;
    }

    public static void main(String[] args) {

    }

}
